public class MovingCount {

    public static void main(String[] args) {
        MovingCount movingCount = new MovingCount();
        System.out.println(movingCount.movingCount(16, 8, 4));
    }

    int m;
    int n;
    int ans = 0;
    int k;
    int[][] temp = {{1, 0}, {0, 1}};
    boolean[][] flag;
    public int movingCount1(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        flag = new boolean[m][n];
        dfs(0,0);
        return ans;
    }

    public void dfs(int i, int j) {
        ++ans;
        flag[i][j] = true;
        for (int[] ints : temp) {
            int x = i + ints[0];
            int y = j + ints[1];
            if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y] && process(x) + process(y) <= k) {
                dfs(x, y);
            }
        }
    }

    public int process(int num) {
        int res = 0;
        while (num != 0) {
            res += num % 10;
            num /= 10;
        }
        return res;
    }

    public int movingCount(int m, int n, int k) {
        boolean[] dp = new boolean[n];
        dp[0] = true;
        boolean last;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            last = false;
            for (int j = 0; j < n; j++) {
                if (!(last || dp[j])) continue;
                if (process(i) + process(j) <= k) {
                    dp[j] = true;
                } else dp[j] = false;
                last = dp[j];
                ans += dp[j] ? 1 : 0;
            }
        }
        return ans;
    }
}
